#ifndef _BINARYHEAP_H
#define _BINARYHEAP_H

#include "../include/cppglobal.h"

template <typename Comparable>
class BinaryHeap{
	public:
		explicit BinaryHeap(int capacity = 100);
		explicit BinaryHeap(const vector< Comparable > & items);
		~BinaryHeap(){
		}
	public:
		bool isEmpty() const;
		const Comparable &findMin() const;
		
		void deleteMin();
		void printH(){
				cout<<"haha"<<endl;
				}
		void deleteMin(Comparable & minItem);

	public:
		void insert(const Comparable &x);

	private:
		void buildHeap();
		void percolateDown(int hole);
	private:
		vector<Comparable> heap;
		int currentSize;
		int maxSize;

};





template<typename Comparable>
BinaryHeap<Comparable>::BinaryHeap(int capacity){
	Comparable temp;
	maxSize = capacity;
	currentSize = 0;
	heap= new Comparable(capacity + 1);
	heap[0] = temp;
}

template<typename Comparable>
BinaryHeap<Comparable>::BinaryHeap( const vector<Comparable> &items){
	for(unsigned int i=0;i<items.size();i++){
		heap[i+1] = items[i];
	}
	currentSize = heap.size() -1;
	buildHeap();
}

template<typename Comparable>
bool
BinaryHeap<Comparable>::isEmpty() const {
	if(currentSize ==0)
		return true;
	else
		return false;
}

template<typename Comparable>
const Comparable &
BinaryHeap<Comparable>::findMin() const {
	return heap.at(1);
}

template<typename Comparable>
void
BinaryHeap<Comparable>::deleteMin(){
	Comparable min;
	deleteMIn(min);
	return ;
}

template<typename Comparable>
void
BinaryHeap<Comparable>::deleteMin( Comparable & minItem){
	minItem = findMin();
	heap[1] = heap[currentSize];
	heap.erase(heap.end() - 1 );
	currentSize = currentSize -1;
	heap.percolateDown(1);
	return ;
}

template<typename Comparable>
void
BinaryHeap<Comparable>::insert(const Comparable &x){
	if(currentSize >= maxSize){
		cout<<"reach the maxSize"<<endl;
		return;
	}
	int hole = ++currentSize;
	for(;hole > 1 && x < heap[hole/2] ;hole = hole /2){
		heap[hole] = heap[hole/2];
	}
	heap[hole] = x;
	return;
}

template<typename Comparable>
void
BinaryHeap<Comparable>::buildHeap(){
	for(int i=currentSize/2;i>0;i--)
		percolateDown(i);
	return ;
}

template<typename Comparable>
void
BinaryHeap<Comparable>::percolateDown(int hole){
	Comparable x = heap.at(hole);
	int nextHole;
	for(;hole*2 <=currentSize;hole = nextHole){
		nextHole = 2*hole;
		if(nextHole != currentSize && heap[nextHole+1] < heap[nextHole]){
			nextHole ++;
		}
		if( heap[nextHole] < x){		
			heap[hole] = heap[nextHole];
		}else
			break;
	}
	heap[hole]=x;
}








#endif
